Alignment of Density Maps in Wasserstein Distance.

In this paper we propose an algorithm for aligning three-dimensional objects when represented as density maps, motivated by applications in cryogenic electron microscopy. The algorithm is based on minimizing the 1-Wasserstein distance between the density maps after a rigid transformation. The induced loss function enjoys a more benign landscape than its Euclidean counterpart and Bayesian optimization is employed for computation. Numerical experiments show improved accuracy and efficiency over existing algorithms on the alignment of real protein molecules. In the context of aligning heterogeneous pairs, we illustrate a potential need for new distance functions.

Alignment of density maps in Wasserstein distance.

In this article, we propose an algorithm for aligning three-dimensional objects when represented as density maps, motivated by applications in cryogenic electron microscopy. The algorithm is based on minimizing the 1-Wasserstein distance between the density maps after a rigid transformation. The induced loss function enjoys a more benign landscape than its Euclidean counterpart and Bayesian optimization is employed for computation. Numerical experiments show improved accuracy and efficiency over existing algorithms on the alignment of real protein molecules. In the context of aligning heterogeneous pairs, we illustrate a potential need for new distance functions.

Moment-based metrics for molecules computable from cryogenic electron microscopy images.

Single-particle cryogenic electron microscopy (cryo-EM) is an imaging technique capable of recovering the high-resolution three-dimensional (3D) structure of biological macromolecules from many noisy and randomly oriented projection images. One notable approach to 3D reconstruction, known as Kam's method, relies on the moments of the two-dimensional (2D) images. Inspired by Kam's method, we introduce a rotationally invariant metric between two molecular structures, which does not require 3D alignment. Further, we introduce a metric between a stack of projection images and a molecular structure, which is invariant to rotations and reflections and does not require performing 3D reconstruction. Additionally, the latter metric does not assume a uniform distribution of viewing angles. We demonstrate the uses of the new metrics on synthetic and experimental datasets, highlighting their ability to measure structural similarity.

Self Fourier shell correlation: properties and application to cryo-ET.

The Fourier shell correlation (FSC) is a measure of the similarity between two signals computed over corresponding shells in the frequency domain and has broad applications in microscopy. In structural biology, the FSC is ubiquitous in methods for validation, resolution determination, and signal enhancement. Computing the FSC usually requires two independent measurements of the same underlying signal, which can be limiting for some applications. Here, we analyze and extend on an approach to estimate the FSC from a single measurement. In particular, we derive the necessary conditions required to estimate the FSC from downsampled versions of a single noisy measurement. These conditions reveal additional corrections which we implement to increase the applicability of the method. We then illustrate two applications of our approach, first as an estimate of the global resolution from a single 3-D structure and second as a data-driven method for denoising tomographic reconstructions in electron cryo-tomography. These results provide general guidelines for computing the FSC from a single measurement and suggest new applications of the FSC in microscopy.

A Bayesian Framework for Cryo-EM Heterogeneity Analysis using Regularized Covariance Estimation.

Proteins and the complexes they form are central to nearly all cellular processes. Their flexibility, expressed through a continuum of states, provides a window into their biological functions. Cryogenic-electron microscopy (cryo-EM) is an ideal tool to study these dynamic states as it captures specimens in non-crystalline conditions and enables high-resolution reconstructions. However, analyzing the heterogeneous distribution of conformations from cryo-EM data is challenging. Current methods face issues such as a lack of explainability, overfitting caused by lack of regularization, and a large number of parameters to tune; problems exacerbated by the lack of proper metrics to evaluate or compare heterogeneous reconstructions. To address these challenges, we present RECOVAR, a white-box method based on principal component analysis (PCA) computed via regularized covariance estimation that can resolve intricate heterogeneity with similar expressive power to neural networks with significantly lower computational demands. We extend the ubiquitous Bayesian framework used in homogeneous reconstruction to automatically regularize principal components, overcoming overfitting concerns and removing the need for most parameters. We further exploit the conservation of density and distances endowed by the embedding in PCA space, opening the door to reliable free energy computation. We leverage the predictable uncertainty of image labels to generate high-resolution reconstructions and identify high-density trajectories in latent space. We make the code freely available at https://github.com/ma-gilles/recovar.

Self Fourier shell correlation: properties and application to cryo-ET.

The Fourier shell correlation (FSC) is a measure of the similarity between two signals computed over corresponding shells in the frequency domain and has broad applications in microscopy. In structural biology, the FSC is ubiquitous in methods for validation, resolution determination, and signal enhancement. Computing the FSC usually requires two independent measurements of the same underlying signal, which can be limiting for some applications. Here, we analyze and extend on an approach proposed by Koho et al. [1] to estimate the FSC from a single measurement. In particular, we derive the necessary conditions required to estimate the FSC from downsampled versions of a single noisy measurement. These conditions reveal additional corrections which we implement to increase the applicability of the method. We then illustrate two applications of our approach, first as an estimate of the global resolution from a single 3-D structure and second as a data-driven method for denoising tomographic reconstructions in electron cryo-tomography. These results provide general guidelines for computing the FSC from a single measurement and suggest new applications of the FSC in microscopy.

Fast principal component analysis for cryo-electron microscopy images.

Principal component analysis (PCA) plays an important role in the analysis of cryo-electron microscopy (cryo-EM) images for various tasks such as classification, denoising, compression, and ab initio modeling. We introduce a fast method for estimating a compressed representation of the 2-D covariance matrix of noisy cryo-EM projection images affected by radial point spread functions that enables fast PCA computation. Our method is based on a new algorithm for expanding images in the Fourier-Bessel basis (the harmonics on the disk), which provides a convenient way to handle the effect of the contrast transfer functions. For N images of size L × L, our method has time complexity O(NL3 + L4) and space complexity O(NL2 + L3). In contrast to previous work, these complexities are independent of the number of different contrast transfer functions of the images. We demonstrate our approach on synthetic and experimental data and show acceleration by factors of up to two orders of magnitude.

Autocorrelation analysis for cryo-EM with sparsity constraints: Improved sample complexity and projection-based algorithms.

The number of noisy images required for molecular reconstruction in single-particle cryoelectron microscopy (cryo-EM) is governed by the autocorrelations of the observed, randomly oriented, noisy projection images. In this work, we consider the effect of imposing sparsity priors on the molecule. We use techniques from signal processing, optimization, and applied algebraic geometry to obtain theoretical and computational contributions for this challenging nonlinear inverse problem with sparsity constraints. We prove that molecular structures modeled as sums of Gaussians are uniquely determined by the second-order autocorrelation of their projection images, implying that the sample complexity is proportional to the square of the variance of the noise. This theory improves upon the nonsparse case, where the third-order autocorrelation is required for uniformly oriented particle images and the sample complexity scales with the cube of the noise variance. Furthermore, we build a computational framework to reconstruct molecular structures which are sparse in the wavelet basis. This method combines the sparse representation for the molecule with projection-based techniques used for phase retrieval in X-ray crystallography.

Super-resolution multi-reference alignment.

We study super-resolution multi-reference alignment, the problem of estimating a signal from many circularly shifted, down-sampled and noisy observations. We focus on the low SNR regime, and show that a signal in ℝ M is uniquely determined when the number L of samples per observation is of the order of the square root of the signal's length ( L = O ( M ) ). Phrased more informally, one can square the resolution. This result holds if the number of observations is proportional to 1/SNR3. In contrast, with fewer observations recovery is impossible even when the observations are not down-sampled (L = M). The analysis combines tools from statistical signal processing and invariant theory. We design an expectation-maximization algorithm and demonstrate that it can super-resolve the signal in challenging SNR regimes.

Random conical tilt reconstruction without particle picking in cryo-electron microscopy.

A method is proposed to reconstruct the 3D molecular structure from micrographs collected at just one sample tilt angle in the random conical tilt scheme in cryo-electron microscopy. The method uses autocorrelation analysis on the micrographs to estimate features of the molecule which are invariant under certain nuisance parameters such as the positions of molecular projections in the micrographs. This enables the molecular structure to be reconstructed directly from micrographs, completely circumventing the need for particle picking. Reconstructions are demonstrated with simulated data and the effect of the missing-cone region is investigated. These results show promise to reduce the size limit for single-particle reconstruction in cryo-electron microscopy.

Ab-initio contrast estimation and denoising of cryo-EM images.

BACKGROUND AND OBJECTIVE: The contrast of cryo-EM images varies from one to another, primarily due to the uneven thickness of the ice layer. This contrast variation can affect the quality of 2-D class averaging, 3-D ab-initio modeling, and 3-D heterogeneity analysis. Contrast estimation is currently performed during 3-D iterative refinement. As a result, the estimates are not available at the earlier computational stages of class averaging and ab-initio modeling. This paper aims to solve the contrast estimation problem directly from the picked particle images in the ab-initio stage, without estimating the 3-D volume, image rotations, or class averages. METHODS: The key observation underlying our analysis is that the 2-D covariance matrix of the raw images is related to the covariance of the underlying clean images, the noise variance, and the contrast variability between images. We show that the contrast variability can be derived from the 2-D covariance matrix and we apply the existing Covariance Wiener Filtering (CWF) framework to estimate it. We also demonstrate a modification of CWF to estimate the contrast of individual images. RESULTS: Our method improves the contrast estimation by a large margin, compared to the previous CWF method. Its estimation accuracy is often comparable to that of an oracle that knows the ground truth covariance of the clean images. The more accurate contrast estimation also improves the quality of image restoration as demonstrated in both synthetic and experimental datasets. CONCLUSIONS: This paper proposes an effective method for contrast estimation directly from noisy images without using any 3-D volume information. It enables contrast correction in the earlier stage of single particle analysis, and may improve the accuracy of downstream processing.

A molecular prior distribution for Bayesian inference based on Wilson statistics.

BACKGROUND AND OBJECTIVE: Wilson statistics describe well the power spectrum of proteins at high frequencies. Therefore, it has found several applications in structural biology, e.g., it is the basis for sharpening steps used in cryogenic electron microscopy (cryo-EM). A recent paper gave the first rigorous proof of Wilson statistics based on a formalism of Wilson's original argument. This new analysis also leads to statistical estimates of the scattering potential of proteins that reveal a correlation between neighboring Fourier coefficients. Here we exploit these estimates to craft a novel prior that can be used for Bayesian inference of molecular structures. METHODS: We describe the properties of the prior and the computation of its hyperparameters. We then evaluate the prior on two synthetic linear inverse problems, and compare against a popular prior in cryo-EM reconstruction at a range of SNRs. RESULTS: We show that the new prior effectively suppresses noise and fills-in low SNR regions in the spectral domain. Furthermore, it improves the resolution of estimates on the problems considered for a wide range of SNR and produces Fourier Shell Correlation curves that are insensitive to masking effects. CONCLUSIONS: We analyze the assumptions in the model, discuss relations to other regularization strategies, and postulate on potential implications for structure determination in cryo-EM.

NMR Assignment through Linear Programming.

Nuclear Magnetic Resonance (NMR) Spectroscopy is the second most used technique (after X-ray crystallography) for structural determination of proteins. A computational challenge in this technique involves solving a discrete optimization problem that assigns the resonance frequency to each atom in the protein. This paper introduces LIAN (LInear programming Assignment for NMR), a novel linear programming formulation of the problem which yields state-of-the-art results in simulated and experimental datasets.

An approximate expectation-maximization for two-dimensional multi-target detection.

We consider the two-dimensional multi-target detection (MTD) problem of estimating a target image from a noisy measurement that contains multiple copies of the image, each randomly rotated and translated. The MTD model serves as a mathematical abstraction of the structure reconstruction problem in single-particle cryo-electron microscopy, the chief motivation of this study. We focus on high noise regimes, where accurate detection of image occurrences within a measurement is impossible. To estimate the image, we develop an expectation-maximization framework that aims to maximize an approximation of the likelihood function. We demonstrate image recovery in highly noisy environments, and show that our framework outperforms the previously studied autocorrelation analysis in a wide range of parameters.

Wilson statistics: derivation, generalization and applications to electron cryomicroscopy.

The power spectrum of proteins at high frequencies is remarkably well described by the flat Wilson statistics. Wilson statistics therefore plays a significant role in X-ray crystallography and more recently in electron cryomicroscopy (cryo-EM). Specifically, modern computational methods for three-dimensional map sharpening and atomic modelling of macromolecules by single-particle cryo-EM are based on Wilson statistics. Here the first rigorous mathematical derivation of Wilson statistics is provided. The derivation pinpoints the regime of validity of Wilson statistics in terms of the size of the macromolecule. Moreover, the analysis naturally leads to generalizations of the statistics to covariance and higher-order spectra. These in turn provide a theoretical foundation for assumptions underlying the widespread Bayesian inference framework for three-dimensional refinement and for explaining the limitations of autocorrelation-based methods in cryo-EM.

Centering Noisy Images with Application to Cryo-EM.

We target the problem of estimating the center of mass of objects in noisy two-dimensional images. We assume that the noise dominates the image, and thus many standard approaches are vulnerable to estimation errors, e.g., the direct computation of the center of mass and the geometric median which is a robust alternative to the center of mass. In this paper, we define a novel surrogate function to the center of mass. We present a mathematical and numerical analysis of our method and show that it outperforms existing methods for estimating the center of mass of an object in various realistic scenarios. As a case study, we apply our centering method to data from single-particle cryo-electron microscopy (cryo-EM), where the goal is to reconstruct the three-dimensional structure of macromolecules. We show how to apply our approach for a better translational alignment of molecule images picked from experimental data. In this way, we facilitate the succeeding steps of reconstruction and streamline the entire cryo-EM pipeline, saving computational time and supporting resolution enhancement.

Cryo-EM reconstruction of continuous heterogeneity by Laplacian spectral volumes.

Single-particle electron cryomicroscopy is an essential tool for high-resolution 3D reconstruction of proteins and other biological macromolecules. An important challenge in cryo-EM is the reconstruction of non-rigid molecules with parts that move and deform. Traditional reconstruction methods fail in these cases, resulting in smeared reconstructions of the moving parts. This poses a major obstacle for structural biologists, who need high-resolution reconstructions of entire macromolecules, moving parts included. To address this challenge, we present a new method for the reconstruction of macromolecules exhibiting continuous heterogeneity. The proposed method uses projection images from multiple viewing directions to construct a graph Laplacian through which the manifold of three-dimensional conformations is analyzed. The 3D molecular structures are then expanded in a basis of Laplacian eigenvectors, using a novel generalized tomographic reconstruction algorithm to compute the expansion coefficients. These coefficients, which we name spectral volumes, provide a high-resolution visualization of the molecular dynamics. We provide a theoretical analysis and evaluate the method empirically on several simulated data sets.

Single-particle cryo-electron microscopy: Mathematical theory, computational challenges, and opportunities.

In recent years, an abundance of new molecular structures have been elucidated using cryo-electron microscopy (cryo-EM), largely due to advances in hardware technology and data processing techniques. Owing to these new exciting developments, cryo-EM was selected by Nature Methods as Method of the Year 2015, and the Nobel Prize in Chemistry 2017 was awarded to three pioneers in the field. The main goal of this article is to introduce the challenging and exciting computational tasks involved in reconstructing 3-D molecular structures by cryo-EM. Determining molecular structures requires a wide range of computational tools in a variety of fields, including signal processing, estimation and detection theory, high-dimensional statistics, convex and non-convex optimization, spectral algorithms, dimensionality reduction, and machine learning. The tools from these fields must be adapted to work under exceptionally challenging conditions, including extreme noise levels, the presence of missing data, and massively large datasets as large as several Terabytes. In addition, we present two statistical models: multi-reference alignment and multi-target detection, that abstract away much of the intricacies of cryo-EM, while retaining some of its essential features. Based on these abstractions, we discuss some recent intriguing results in the mathematical theory of cryo-EM, and delineate relations with group theory, invariant theory, and information theory.

Steerable ePCA: Rotationally Invariant Exponential Family PCA.

In photon-limited imaging, the pixel intensities are affected by photon count noise. Many applications require an accurate estimation of the covariance of the underlying 2-D clean images. For example, in X-ray free electron laser (XFEL) single molecule imaging, the covariance matrix of 2-D diffraction images is used to reconstruct the 3-D molecular structure. Accurate estimation of the covariance from low-photon-count images must take into account that pixel intensities are Poisson distributed, hence the classical sample covariance estimator is highly biased. Moreover, in single molecule imaging, including in-plane rotated copies of all images could further improve the accuracy of covariance estimation. In this paper we introduce an efficient and accurate algorithm for covariance matrix estimation of count noise 2-D images, including their uniform planar rotations and possibly reflections. Our procedure, steerable ePCA, combines in a novel way two recently introduced innovations. The first is a methodology for principal component analysis (PCA) for Poisson distributions, and more generally, exponential family distributions, called ePCA. The second is steerable PCA, a fast and accurate procedure for including all planar rotations when performing PCA. The resulting principal components are invariant to the rotation and reflection of the input images. We demonstrate the efficiency and accuracy of steerable ePCA in numerical experiments involving simulated XFEL datasets and rotated face images from Yale Face Database B.

Reducing bias and variance for CTF estimation in single particle cryo-EM.

When using an electron microscope for imaging of particles embedded in vitreous ice, the recorded image, or micrograph, is a significantly degraded version of the tomographic projection of the sample. Apart from noise, the image is affected by the optical configuration of the microscope. This transformation is typically modeled as a convolution with a point spread function. The Fourier transform of this function, known as the contrast transfer function (CTF), is oscillatory, attenuating and amplifying different frequency bands, and sometimes flipping their signs. High-resolution reconstruction requires this CTF to be accounted for, but as its form depends on experimental parameters, it must first be estimated from the micrograph. We present a new method for CTF estimation based on multitaper techniques that reduce bias and variance in the estimate. We also use known properties of the CTF and the background power spectrum to further reduce the variance through background subtraction and steerable basis projection. We show that the resulting power spectrum estimates better capture the zero-crossings of the CTF and yield accurate CTF estimates on several experimental micrographs.